#define _CRT_SECURE_NO_WARNINGS 1
void pushback(LN**head,LN** tail, LN* node) {
    if (*tail == NULL) {

        *head=*tail = node;
    } else {
        (*tail)->next = node;
        *tail = node;
    }
}
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) {
    if (list1 == NULL)
        return list2;
    else if (list2 == NULL)
        return list1;
    else if (list1 == NULL && list2 == NULL)
        return NULL;
    else {
        LN *cur1 = list1, *cur2 = list2;
        LN *newhead = NULL, *newtail = NULL;
        while (cur1 && cur2) {
            pushback(&newhead,&newtail,cur1->val < cur2->val ? cur1 : cur2);
            if (cur1->val < cur2->val) {
                cur1 = cur1->next;
            } else {
                cur2 = cur2->next;
            }
        }
        if(cur1)
        {
            newtail->next=cur1;
            newtail=cur1;
        }
        else
        {
            newtail->next=cur2;
            newtail=cur2;
        }
         return newhead;
    }
   
}